package 字符串系列;

import java.util.*;

public class ReverseWords {
    //解法一：正则表达式
    public String reverseWords(String s) {
        s = s.trim();   // 除去开头和末尾的空白字符
        // 正则匹配连续的空白字符作为分隔符分割
        String[] a = s.split("\\s+");
        List<String> wordList = Arrays.asList(a);

        Collections.reverse(wordList);
        return String.join(" ",wordList);
    }
    //解法二：
    public String reverseWords1(String s) {
        s = s.trim();   // 除去开头和末尾的空白字符
        char[] Ch = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int right = Ch.length-1;
        for(int i = Ch.length-1; i >= 0; i--){
            //System.out.println(i+":"+Ch[i]);
            if(Ch[i]==' '){
                //System.out.println("i="+i+",right="+right+",rigth-i-1="+(right-i+1));
                sb.append(new String(Ch,i,right-i+1).trim());
                sb.append(Ch[i]);
                while(Ch[i-1]==' '){
                    i--;
                }
                right = i;
            }
            if(i==0){
                sb.append(new String(Ch,0,right-i).trim());
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        ReverseWords rw = new ReverseWords();
        String a = rw.reverseWords1("  hello world  ");
        System.out.println("======================");
        String b = rw.reverseWords1("the sky is blue");
        System.out.println(a);
        System.out.println(b);
    }
}
class Solution {
    public String reverseWords(String s) {
        int left = 0, right = s.length() - 1;
        // 去掉字符串开头的空白字符
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }

        // 去掉字符串末尾的空白字符
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        Deque<String> d = new ArrayDeque<String>();
        StringBuilder word = new StringBuilder();

        while (left <= right) {
            char c = s.charAt(left);
            if ((word.length() != 0) && (c == ' ')) {
                // 将单词 push 到队列的头部
                d.offerFirst(word.toString());
                word.setLength(0);
            } else if (c != ' ') {
                word.append(c);
            }
            ++left;
        }
        d.offerFirst(word.toString());

        return String.join(" ", d);
    }
}
